package likou.dtgh.beibao;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/09/03 22:18
 */

/**
 * 一个旅行者有一个最多能装M工具的背包，
 * 现在有n件物品，它们的重量分别是W1,W1，
 * 它们的价值为C1,C2，求旅行者能获得最大的总价值。
 */
public class _1 {
    public static void main(String[] args) {
        _1 one = new _1();
        System.out.println(one.getMax(15, new int[]{2, 3, 4, 7}, new int[]{1, 3, 5, 9}));
    }

    public int getMax(int M, int[] W, int[] C) {
        int[] res = new int[M + 1];
        for (int i = 0; i < W.length; i++) {
            for (int j = M; j >= 1; j--) {
                if (j>=W[i]){
                    res[j] = Math.max(res[j], res[j - W[i]] + C[i]);
                }
            }
        }
        return res[M];
    }
}
